package 力扣._32最长有小括号;

import java.util.Arrays;

class Solution {
    // 超时
    public int longestValidParentheses(String s) {
        int len = s.length();
        int max = 0;

        // dp[i][j] 表示 s[i:j] 是否是有效的括号
        boolean[][] dp = new boolean[len][len];
        // dp[i][j] = dp[i+1][k-1] && dp[k+1][j] && s[i] == '(' && s[k] == ')', k = i+1, i+3, i+5, ... <= j

        for (int i = len - 1; i >= 0; i--) {
            if(s.charAt(i)!='(')
                continue;
            for (int j = i + 1; j < len; j += 2) {
                if(s.charAt(j)!=')')
                    continue;
                if ((j - i + 1) % 2 == 1) {
                    dp[i][j] = false;
                } else if (j - i + 1 == 2) {
                    dp[i][j] = s.substring(i, j + 1).equals("()");

                } else {
                    for (int k = i + 1; k <= j; k += 2) {
                        // 若该序列已可行，则结束该循环
                        if (dp[i][j])
                            break;
                        // 右边子括号为空
                        if (k == j) {
                            dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == '(' && s.charAt(j) == ')';

                        } else {
                            // 若左侧括号中内容为空，
                            if(i + 1>k - 1)
                                dp[i + 1][k - 1] = true;
                            dp[i][j] = dp[i + 1][k - 1] && dp[k + 1][j] && s.charAt(i) == '(' && s.charAt(k) == ')';

                        }
                    }
                }
                if (dp[i][j]) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        return max;

    }

    public static void main(String[] args) {
        int i = new Solution().longestValidParentheses("))(()()()))(");
        System.out.println(i);
    }
}